package history.hot100;

// 64. 最小路径和

/**
 * 1. dp[i][j]表示到达(i,j)最小代价
 * 2. dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1])+grid[i][j]
 * 3. dp[i][0] = dp[i-1][0]+grid[i][0]
 *    dp[0][j] = dp[0][j-1]+grid[0][j]
 * 4. 从前往后，从上往下
 * 5.
 */
public class LeetCode_64 {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length<=0 || grid[0].length<=0) return 0;
        int RLength = grid.length, CLength = grid[0].length;
        int [][]state = new int[RLength][CLength];
        state[0][0] = grid[0][0];
        for (int i = 1; i < RLength; i++)
            state[i][0] = state[i-1][0]+grid[i][0];
        for (int i = 1; i < CLength; i++)
            state[0][i] = state[0][i-1]+grid[0][i];
        for (int i = 1; i < RLength; i++) {
            for (int j = 1; j < CLength; j++) {
                state[i][j] = Math.min(state[i-1][j], state[i][j-1])+grid[i][j];
            }
        }
        return state[RLength-1][CLength-1];
    }
}
